/*
 * @lc app=leetcode.cn id=1005 lang=cpp
 *
 * [1005] K 次取反后最大化的数组和
 */

// @lc code=start
class Solution
{
    static bool cmp(int a, int b)
    {
        //从大到小排序
        return abs(a) > abs(b);
    }

public:
    int largestSumAfterKNegations(vector<int> &nums, int k)
    {
        //k次取反的最大值 很简单吧 先排序 从小到大依次取反
        //我傻逼了 没看题 他可以对同一个元素反转多次
        //首先对于负数 需要将绝对值大的负数反转 如果多了 就将小的非负数反转
        sort(nums.begin(), nums.end(), cmp); //按绝对值从大到小排序
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] < 0 && k > 0)
            {
                k--;
                nums[i] *= -1;
            }
        }
        //如果k还有剩余 如果偶数直接反转不变 为奇数选个最小的正数
        if (k % 2 == 1)
        {
            nums[nums.size() - 1] *= -1;
        }
        int res = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            res += nums[i];
        }
        return res;
    }
};
// @lc code=end
